package week_01;

public class NumMatrix {

    private int[][] sum;

    public NumMatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        sum = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //𝑆𝑖−1𝑗+𝑆𝑖𝑗−1−𝑆𝑖−1𝑗−1+𝐴[𝑖][𝑗]
                //sum[i][j] = get_sum(i - 1, j) + get_sum(i, j - 1) - get_sum(i - 1, j - 1) + matrix[i][j];
                sum[i][j] = getSum(i - 1, j) + getSum(i, j - 1) - getSum(i - 1, j - 1) + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        //𝑆𝑖𝑗−𝑆𝑖𝑞−1−𝑆𝑝−1𝑗+𝑆[𝑝−1][𝑞−1]
        //return get_sum(row2, col2) - get_sum(row1 - 1, col2) - get_sum(row2, col1 - 1) + get_sum(row1 - 1, col1 - 1);
        return getSum(row2, col2) - getSum(row2, col1 - 1) - getSum(row1 - 1, col2) + getSum(row1 - 1, col1 - 1);
    }

    public int getSum(int i, int j) {
        if (i >= 0 && j >= 0) return sum[i][j];
        return 0;
    }
}
